// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem287.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\287.寻找重复数.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-04-08 16:34:36
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-04-08 16:35:29
 */
/*
 * @lc app=leetcode.cn id=287 lang=cpp
 *
 * [287] 寻找重复数
 */

// @lc code=start
class Solution {
public:
    // int findDuplicate(vector<int>& nums) {
    //     unordered_map<int,int> map;
    //     for(int i = 0 ; i < nums.size();i++)
    //     {
    //         if(map[nums[i]] > 0)
    //             return nums[i];
    //         map[nums[i]]++;
    //     }
    //     return 0;
    // }

    // 使用快慢指针。
//     int findDuplicate(vector<int>& nums) 
//     {
//         int fast = 0, slow = 0;

//         do { // 为避免初始化nums[slow] = nums[fast] 用do-while
//             slow = nums[slow];
//             fast = nums[nums[fast]];
//         } while (nums[slow] != nums[fast]);

//         fast = 0; // 第一次交点之后，fast从0开始

//         while (nums[slow] != nums[fast])  //两个指针一次走一步
//         {
//             slow = nums[slow];
//             fast = nums[fast];
//         }
//         return nums[slow];
//    }

        // https://blog.csdn.net/qq_33521184/article/details/109035520?utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.control&dist_request_id=&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.control
        // 因为是 n+1个整数中有n个不重复,所以可以将这个数组虚拟化为一个链表的形式。
        // 例子：1，3，4，2，2
        // 下标             值
        //  0               1
        //  1               3
        //  2               4
        //  3               2
        //  4               2
        // 这样虚拟化为链表 0->1->3->2->4->2..    这样就相当于是求链表是否有环，即环的头结点。

        int findDuplicate(vector<int>& nums)
        {
            int slow = 0;
            int fast = 0;
            while(true)
            {
                slow = nums[slow];
                fast = nums[nums[fast]];

                if(slow == fast)
                    break;
            }

            fast = 0;
            while(true)
            {
                slow = nums[slow];
                fast = nums[fast];
                if(slow == fast)
                {
                    break;
                }
            }
            return slow;
        }




};
// @lc code=end

